/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package minimalshift;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;
import org.jgrapht.Graph;
import org.jgrapht.alg.EdmondsKarpMaximumFlow;
import org.jgrapht.graph.DefaultDirectedWeightedGraph;

/**
 *
 * @author Michal
 */
public class GraphManager {

	private final int PENALIZATION = 1;
	private final int SOURCE = 0;
	private final int SINK = Integer.MAX_VALUE;
	private List<Shift> shifts;
	private List<Integer> reqs;
	private int len;
	private int breakCycle;

	public GraphManager(List<Shift> shifts, List<Integer> reqs, int len) {
		this.reqs = reqs;
		this.len = len;
		this.shifts = new LinkedList<>();
		fillWeekWithShifts(shifts);
	}

	/**
	 * Vytvori smeny i pro dalsi dny
	 */
	private void fillWeekWithShifts(List<Shift> shifts) {
		int total = len * reqs.size();
		int days = total / 60 / 24;
		for (int i = 0; i < days; i++) {
			for (Shift s : shifts) {
				int startTime = (s.getStart() + i * 24 * 60) % total;
				int endTime = (s.getFinish() + i * 24 * 60) % total;
				Shift newShift = new Shift(startTime, s.getLen(), endTime);
				this.shifts.add(newShift);
			}
		}
	}

	public Graph<Integer, GraphEdge> getGraph() {
		int breakTime = 00;
		List<Shift> reduced = breakCycle(breakTime);
		return createGraph(reduced, breakTime);
	}

	public Map<GraphEdge, Double> minCostMaxFlow() {
		Map<GraphEdge, Double> solution = null;
		int bestCost = Integer.MAX_VALUE;

		// pocet moznych startu za den
		int cycleNumber = 24 * 60 / len;

		//udelam pocatecni reseni
		DefaultDirectedWeightedGraph<Integer, GraphEdge> graph = null;
		for (int i = 0; i < cycleNumber; i++) {
			int breakTime = i * len;
			List<Shift> reduced = breakCycle(breakTime);
			graph = createGraph(reduced, breakTime);
			MinCostMaxFlow solver = new MinCostMaxFlow(graph);
			Map<GraphEdge, Double> temp = solver.getResult(SOURCE, SINK);
			int cost = GraphManager.getCost(temp);
			if (cost < bestCost) {
				this.breakCycle = breakTime / len;
				solution = temp;
				bestCost = cost;
			}
		}
		//Greedy
		Set<GraphEdge> used = new HashSet<>();
		while (true) {
			GraphEdge edge = getShiftFromSets(used, solution);
			if (edge == null) {
				break;
			}
			DefaultDirectedWeightedGraph<Integer, GraphEdge> newGraph = getClone(graph);
			newGraph.removeEdge(edge);
			MinCostMaxFlow solver = new MinCostMaxFlow(newGraph);
			Map<GraphEdge, Double> temp = solver.getResult(SOURCE, SINK);
			int cost = GraphManager.getCost(temp);
			if (cost < bestCost) {
				graph = newGraph;
				solution = temp;
				bestCost = cost;
			}
			used.add(edge);
		}

		return solution;
	}

	private DefaultDirectedWeightedGraph<Integer, GraphEdge> createGraph(List<Shift> shifts, int breakTime) {
		DefaultDirectedWeightedGraph<Integer, GraphEdge> graph = new DefaultDirectedWeightedGraph<>(GraphEdge.class);

		//Vyrobim vrcholy
		graph.addVertex(SINK); //prvni -> source
		for (int i = 1; i <= reqs.size(); i++) {
			graph.addVertex(i);
		}
		int breakVertex = reqs.size() + 1;
		graph.addVertex(breakVertex);
		graph.addVertex(SOURCE); // posledni -> sink

		int breakCycle = breakTime / len;
		if (breakCycle == 0) {
			breakCycle = reqs.size();
		}

		// pridame smeny
		for (Shift s : shifts) {
			GraphEdge toAdd = new GraphEdge(true, 1);
			int from = s.getStart() / len; //+1 protoze jsou od jedny
			if(from==0){
				from=24;
			}
			int to = s.getFinish() / len; // +1 protoze jsou od jedny
			if(to==0){
				to=24;
			}
			if (to == breakCycle) {
				to = breakVertex;
			}
			graph.addEdge(from, to, toAdd);
			graph.setEdgeWeight(toAdd, Double.MAX_VALUE);
		}

		// Pridam hrany na dalsi a predchozi cyklus (kvuli nalezeni i neoptimalniho reseni
		for (int i = 1; i <= reqs.size(); i++) {
			// hrana dopredu povede na ten posledni node
			int node = (i + 1) % reqs.size();
			if(node==0){
				node=24;
			}
			if (node == breakCycle) {
				addForwEdge(graph, i, breakVertex);
				addBackEdge(graph, i, breakVertex);
			} // pridame ji normalne
			else {
				addForwEdge(graph, i);
				addBackEdge(graph, i);
			}
		}

		//spocitame zmeny v smenach (tj kolik by jich melo odejit a kolik prijit)
		List<Integer> reqChanges = new LinkedList<>();
		int prev = reqs.get(reqs.size() - 1);
		for (int r : reqs) {
			reqChanges.add(r - prev);
			prev = r;
		}

		//pridame vylez na konci
		GraphEdge lastEdge = new GraphEdge(false, 0);
		graph.addEdge(breakVertex, SINK, lastEdge);
		int finalWeight = reqs.get(breakCycle - 1);
		int reqChangeBefore = reqChanges.get(breakCycle-1);
		if (finalWeight > 0) {
			graph.setEdgeWeight(lastEdge, finalWeight-reqChangeBefore);
		}

		//Pridame zdroje a spotrebice
		int i = 0;
		for (int r : reqChanges) {
			i++;
			if (i == breakCycle) {
				GraphEdge toAdd = new GraphEdge(false, 0);
				graph.addEdge(SOURCE, i, toAdd);
				int weight = reqs.get(breakCycle - 1);
				if (weight == 0) {
					continue;
				}
				graph.setEdgeWeight(toAdd, weight);
				continue;
			}
			if (r == 0) {
				continue;
			}
			if (r > 0) {
				GraphEdge toAdd = new GraphEdge(false, 0);
				graph.addEdge(SOURCE, i, toAdd);
				graph.setEdgeWeight(toAdd, r);
			} else {
				GraphEdge toAdd = new GraphEdge(false, 0);
				graph.addEdge(i, SINK, toAdd);
				graph.setEdgeWeight(toAdd, -1 * r);
			}
		}

		return graph;
	}

	public List<Integer> getReqs() {
		return reqs;
	}
	
	public int getBreakCycle(){
		return breakCycle;
	}

	public static int getCost(Map<GraphEdge, Double> map) {
		int cost = 0;
		for (Map.Entry<GraphEdge, Double> e : map.entrySet()) {
			cost += e.getKey().getCost() * e.getValue();
		}
		return cost;
	}

	public static DefaultDirectedWeightedGraph<Integer, GraphEdge> getClone(DefaultDirectedWeightedGraph<Integer, GraphEdge> normal) {
		DefaultDirectedWeightedGraph<Integer, GraphEdge> newGraph =
				new DefaultDirectedWeightedGraph<>(GraphEdge.class);

		for (int i : normal.vertexSet()) {
			newGraph.addVertex(i);
		}

		for (GraphEdge e : normal.edgeSet()) {
			//GraphEdge copy = new GraphEdge(e.isShift(),e.getCost());
			newGraph.addEdge(normal.getEdgeSource(e), normal.getEdgeTarget(e), e);
			//newGraph.setEdgeWeight(copy,normal.getEdgeWeight(e));
		}

		return newGraph;
	}

	/**
	 * Rozbije cykly - vsechny smeny, ktere zasahujou do daneho casu vymaze
	 */
	private List<Shift> breakCycle(int time) {
		List<Shift> curShifts = new LinkedList<>();
		for (Shift s : shifts) {
			int start = s.getStart();
			int finish = s.getFinish();
			if (start < time && finish > time) {
				continue;
			}
			if (finish - start < 0) {
				if (finish > time || start < time) {
					continue;
				}
			}
			curShifts.add(s);
		}
		return curShifts;
	}

	private GraphEdge getShiftFromSets(Set<GraphEdge> notIn, Map<GraphEdge, Double> in) {
		GraphEdge toReturn = null;
		for (Map.Entry<GraphEdge, Double> e : in.entrySet()) {
			if (!(e.getValue() > 0)) {
				continue;
			}
			if (notIn.contains(e.getKey())) {
				continue;
			}
			return e.getKey();
		}
		return toReturn;
	}

	private void addBackEdge(DefaultDirectedWeightedGraph<Integer, GraphEdge> graph, int i, int j) {
		GraphEdge toAdd = new GraphEdge(false, PENALIZATION, true);
		graph.addEdge(j, i, toAdd);
		graph.setEdgeWeight(toAdd, Double.MAX_VALUE);
	}

	private void addBackEdge(DefaultDirectedWeightedGraph<Integer, GraphEdge> graph, int i) {
		GraphEdge toAdd = new GraphEdge(false, PENALIZATION, true);
		int node = (i + 1) % reqs.size();
		if (node == 0) {
			node = 24;
		}
		graph.addEdge(node, i, toAdd);
		graph.setEdgeWeight(toAdd, Double.MAX_VALUE);
	}

	private void addForwEdge(DefaultDirectedWeightedGraph<Integer, GraphEdge> graph, int i) {
		GraphEdge toAdd = new GraphEdge(false, PENALIZATION);
		int node = (i + 1) % reqs.size();
		if (node == 0) {
			node = 24;
		}
		graph.addEdge(i, node, toAdd);
		graph.setEdgeWeight(toAdd, Double.MAX_VALUE);
	}

	private void addForwEdge(DefaultDirectedWeightedGraph<Integer, GraphEdge> graph, int i, int j) {
		GraphEdge toAdd = new GraphEdge(false, PENALIZATION);
		graph.addEdge(i, j, toAdd);
		graph.setEdgeWeight(toAdd, Double.MAX_VALUE);
	}
}
